1. Field
The present disclosed embodiments relate generally to computing device communications, and more specifically to apparatus and methods of rendering a webpage.
2. Background
Linked data structures include nodes distributed in memory where each node includes at least one pointer (or link) to another node that identifies a location of another node in memory. Linked lists and tree type linked data structures are two examples of linked data structures. Typically, linked data structures are modified by changing the pointers or links between nodes, while the nodes themselves remain in the same physical location in memory.
Utilizing or modifying a linked data structure is performed via a method called traversal, which involves the computational process of moving through the linked data structure from node to node in a specified order (or traversal order) and processing each node as it is traversed. Traversal order is dictated by a traversal algorithm, which includes a set of ordered rules specifying what type of node is to be traversed next in the traversal order. For instance, one traversal algorithm can, at each node, look for the following types of nodes and traverse to the first of these nodes that exists: (1) first child; (2) next sibling; and (3) closest ancestor's sibling, where children, siblings, and parents are defined via a conceptual representation of a linked data structure such as FIG. 2. If none of these types can be found, then the traversal is complete.
To better illustrate this, we can look at a webpage (FIG. 1) and its underlying document object module (DOM) tree (FIG. 2), which illustrates one instance where a tree type linked data structure is used in practice. FIG. 2 shows a conceptualization of the DOM tree showing parent and child relationships between nodes, but not showing the various links between nodes. FIG. 1 is a simplified webpage having 9 elements 102, 104, 106, 108, 110, 112, 114, 116, 118 that are rendered from a DOM tree illustrated in FIG. 2 having 9 nodes 202, 204, 206, 208, 210, 212, 214, 216, 218. The nodes correspond to the webpage elements as follows: 202→102; 204→104; 206→106; 208→108; 210→110; 212→112; 214→114; 216→116; and 218→118. A webpage element within another element is said to be a ‘child’ of the containing element. For instance, windows 104 and 110 are within window 102 and are thus the nodes representing these elements are illustrated as children 204, 210 of node 202 in the DOM tree. The containing element (e.g., 202) is known as the ‘parent.’ A node may have multiple children, but only one parent. Nodes with the same parent node are referred to as ‘siblings.’ For instance, nodes 204 and 210 are siblings, as are 214 and 216. The node at the top of the tree (e.g., 202), which is the only node without a parent, is referred to as the root node.
Typically, nodes in a linked data structure include a link to one or more of the following nodes: parent, first child, previous child, next sibling, previous sibling. For example, node 204 is a parent to nodes 206 and 208. Nodes 206 and 208 are siblings (although these links are not illustrated in the conceptualization of the tree type linked data structure). Node 208 is a next sibling to node 206 and node 206 is a previous sibling to node 208 (these links are also not illustrated). Nodes 214 and 216 are children of node 206. Node 214 is a first child of node 206 and node 216 is a last child of node 206.
In FIG. 2 one can see that the traversal algorithm described above ((1) first child, (2) next sibling, (3) ancestor's sibling) leads to the following traversal order: 202, 204, 206, 214, 216, 208, 218, 210, 212. For instance, at node 204, the first child is 206 and so the algorithm traverses to node 206. At node 214, there is no first child, but there is a next sibling, node 216. At node 216 there is neither a first child, nor a next sibling, so the algorithm traverses up a chain of parents (ancestors) until a parent's sibling is found. In this case, 208 is a sibling to 206, which is the parent (an ancestor) of 216. As a further example, for node 218, there is neither a first child, nor a next sibling, so the algorithm traverses up the chain of parents until a parent's sibling is found; this happens to be node 210, which is a sibling to node 204 which is a parent of the parent of node 218. Eventually, at node 212, neither a first child, a next sibling, nor a sibling of any parent above node 212 exists, so the algorithm has traversed all nodes in the linked data structure and thus traversal is complete. This exemplary traversal order is unique to the illustrated tree type linked data structure of FIGS. 2 and 8 and unique to the traversal algorithm described earlier in this paragraph. In other embodiments, different traversal orders can result from different types of linked data structures and/or different traversal algorithms.
Traversing linked data structures is applicable in a variety of circumstances, such as the rendering of webpages via traversal of DOM trees, and updating of dynamic web pages via traversal and manipulation of DOM trees. The DOM is a convention used to represent and interact with objects in HTML, XHTML, and XML documents. The DOM presents web documents to a program such as a web browser, or to a web developer during programming, as a tree hierarchy having nodes and relationships between nodes. The DOM can thus be used to analyze, manipulate, and render a web document. The DOM is platform and language agnostic, enabling this convention to be used across a wide range of platforms and software languages.
To render a webpage, most web browsers download the HTML document into memory, and parse it into DOM nodes having relations to each other (e.g., parent, child, sibling), where the nodes and their relations together form a DOM tree. Once the DOM tree has been parsed, the web browser traverses the DOM tree and renders the document (e.g., paint to a display, convert to PDF, present on Braille system, or read aloud via synthesized voice, to name a few non-limiting examples).
When the DOM tree is traversed and data from each node is processed, this data is first temporarily stored in a cache for processing (e.g., a CPU cache). This cache has limited space, and thus large and complex linked data structures (e.g., complex web documents) cannot be buffered as a whole in the cache—instead the linked data structure is temporarily stored piecemeal in cache and processed piecemeal sometimes delaying traversal and manipulation of the linked data structure. In the case of web documents this can mean increased rendering times.
Current attempts to improve the speed of traversal involve prefetching, where node data is loaded from memory into the cache before it is needed. The processor is thus able to read node data from cache rather than from memory, and thus traversal latency is reduced.
Prefetch algorithms can either be carried out in hardware or software. Hardware pretching often involves algorithms that prefetch node data based on a previous traversal path—using heuristics to predict likely accesses often based on recent access patterns. On subsequent traversals, the algorithm can often effectively predict where in memory to find nodes in order to prefetch them into the cache.
Implementing hardware prefetching allows arbitrary prefetching problems to be solved quite effectively but at a power cost and without being tailored to the prefetching—it merely knows that it is accessing memory in a certain pattern. The software on the other hand knows that it is performing linked data structure traversal, so it can be tailored to more efficiently perform this task (e.g., more efficiently guess which node is to be traversed next).
Software-based prefetching has the potential to consume less energy than hardware-based methods, however arbitrary heuristics-based prefetching algorithms are typically not efficient to implement in software and would consume more processing time to train and predict prefetch locations than the benefit that such prefetching would afford. Simple prefetching algorithms have been implemented in software given array type data structures, where any node implies a node memory address for all other nodes in the array. In such a data structure, logically adjacent nodes have adjacent addresses. Thus, if nodes are accessed in order, the address of the next node in the linked data structure (according to a given traversal order) can be inferred since the pattern of node addresses is consistent. However, this implied node memory address does not exist for many types of data structures including a typical DOM tree for a webpage. In these cases, there is little pattern to the address of a next node relative to a previous node in the traversal order.
There is therefore a need in the art for a method to traverse large, complex, and nonlinear linked data structures (e.g., DOM trees) using low-power prefetching.